package leetcode_141_160;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 能在常数时间内检索到最小元素的栈。
 */
public class MinStack {
    /**
     * 初始思路，list第 i 个数字代表，stack中被添加进i个数字时的最小值
     * 4ms
     * beat  96%
     * 看了一下高解，和我区别不是很大
     */
    //最小值按先后的排序集合
    private LinkedList<Integer> list;

    private int size = 0;

    LinkedList<Integer> stack;

    public MinStack() {
        stack = new LinkedList<>();
        list = new LinkedList<>();
    }

    /**
     * 将元素val推入堆栈。
     */
    public void push(int val) {
        stack.add(val);
        if (list.size() == 0)
            list.add(val);
        else if (val <= list.getLast())
            list.addLast(val);
        else
            list.addLast(list.getLast());
    }

    /**
     * 删除堆栈顶部的元素。
     */
    public void pop() {
        stack.removeLast();
        list.removeLast();
    }

    /**
     * 获取堆栈顶部的元素
     */
    public int top() {
        return stack.getLast();
    }

    /**
     * 获取堆栈中的最小元素。
     */
    public int getMin() {
        if (list.size() == 0)
            return 0;
        return list.getLast();
    }
}
